public class Test3 {
    //leetcode 746 使用最小花费爬楼梯

    /**
     * 方法一：以dp数组中的第i个位置为结束的爬楼梯的花费
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        //状态表示，dp[i]表示以该台阶结尾的花费
        //状态转移方程：dp[i] = Math.min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]))
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min((dp[i-1] + cost[i-1]),(dp[i-2] + cost[i-2]));
        }
        return dp[n];
    }

    /**
     * 方法二：以dp数组中的第i个位置为起始位置，爬到楼梯顶部分费用
     * @param cost
     * @return
     */
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        //状态表示，dp[i]表示以该台阶为开始的花费
        //状态转移方程：dp[i] = Math.min(dp[i+1],dp[i+2]) + cost[i]
        //数组初始化，对最后连个数组的元素进行初始化
        dp[n-1] = cost[n-1]; dp[n-2] = cost[n-2];
        for (int i = n-3; i >= 0; i--) {
            dp[i] = Math.min(dp[i+1],dp[i+2]) + cost[i];
        }
        //因为题目中给出了，可以选择下标为0或者1的台阶开始爬楼梯
        return Math.min(dp[0],dp[1]);
    }
}
